package com.fengdi.publicObject;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;


/**
 * @Description 前缀树
 * @Date 14:08
 */
public class TrieTree {
    private final TrieNode root;

    public TrieTree() {
        this.root = new TrieNode();
    }

    /**
     * @Description 根据单词列表创建前缀树
     * @Date 2025/6/18
     * @param words: 单词列表
     * @return 前缀树的根节点
     */
    public static TrieTree createTree(String[] words) {
        TrieTree tree = new TrieTree();
        // 插入节点
        for (String s : words) {
            TrieNode p = tree.root;
            char[] chs = s.toCharArray();
            for (char c : chs) {
                int cASCII = (int) (c - 'a');
                if (p.childs[cASCII] == null) {
                    // 不存在当前子节点，创建子节点
                    TrieNode node = new TrieNode(c);
                    p.childs[cASCII] = node;
                }
                //节点存在继续向下
                p = p.childs[cASCII];
            }
            p.isEnd = true;
        }
        return tree;
    }

    /**
     * @Description 插入一个字符串到前缀树中
     * @Date 2025/6/18
     * @param s 需要插入的字符串
     */
    public void insert(String s) {
        if(s.isEmpty()) return;

        TrieNode p = this.root;
        char[] chs = s.toCharArray();

        for(char ch : chs) {
            int chASCII = (int) ch - 'a';
            if(p.childs[chASCII] == null) {
                TrieNode node = new TrieNode(ch);
                p.childs[chASCII] = node;
            }
            p = p.childs[chASCII];
        }
        p.isEnd = true;
    }

    /**
     * @Description 搜索一个字符串是否在前缀树中
     * @Date 2025/6/18
     * @param str 检索的字符串
     * @return  是否存在
     */
    public boolean searchStr(String str) {
        if (str.isEmpty() || str.equals(" ")) return true;
        char[] chars = str.toCharArray();
        TrieNode p = this.root;
        for(char c : chars) {
            if(p.childs[c - 'a'] == null) {
                return false;
            }
            p = p.childs[c - 'a'];
        }
        return true;
    }

    /**
     * @Description 输出前缀树的广度优先遍历序列
     * @Date 2025/6/18
     * @return 序列字符串
     */
    public String toString() {
        ArrayList<Character> chars = new ArrayList<>();
        this.bfs(this.root, chars);
        return chars.toString();
    }

    /**
     * @Description 层序遍历前缀树
     * @Date 2025/6/18
     * @param root 前缀树根节点
     * @param chars 要存入的结果列表
     */
    private void bfs(TrieNode root, ArrayList<Character> chars) {
        if (root == null) return;

        Queue<TrieNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            TrieNode node = queue.poll();
            if(node != null && node.value != ' ') {
                chars.add(node.value);
            }

            if (node != null) {
                for(TrieNode child : node.childs) {
                    if(child != null) {
                        queue.offer(child);
                    }
                }
            }
        }
    }

}
